package net.zjitc.myTree;

/**
 * Created by Administrator on 2017/5/4.
 */
/*定义一个类，主要是实现二叉树的增、删、改、查*/
public class LinkedTree<E> implements MyBinaryTree<E>{
   /* @Override
    public void creat(E val, TreeNode<E> lChild, TreeNode<E> rChild) {

    }*/
   /*使用一个head头接点来指向二叉树的根结点，在找二叉树的时候可通过head找到所有*/
   TreeNode<E> head = null;
  /*初始化的时候自动创建一个二叉树*/
    public LinkedTree(){
    }

    public LinkedTree(E val, TreeNode<E> lChild, TreeNode<E> rChild){
            /*将根结点赋值给头结点*/
            TreeNode<E> p = new TreeNode<>(val,lChild,rChild);
            head = p ;
    }

    // 获得左子树(获得树根结点的左子树)
    @Override
    public TreeNode<E> getLChild(TreeNode<E> p) {
        TreeNode<E> temp = p.getlChild();
        return temp;
    }

    @Override
    public TreeNode<E> getRChild(TreeNode<E> p) {
        return p.getrChild();
    }

    /**
     * 插入一个节点，
     * @param val
     * @param p
     */
    @Override
    public void insertL(E val, TreeNode<E> p) {
     //构造一个节点
        TreeNode<E> temp = new TreeNode<>(val,null,null);
        /*先将p的左孩子赋值给temp的左孩子*/
        temp.setlChild(p.getlChild());
        /*再将temp赋值给p的左孩子*/
        p.setlChild(temp);
    }

    @Override
    public void insertR(E val, TreeNode<E> p) {
//构造一个节点
        TreeNode<E> temp = new TreeNode<>(val,null,null);
        /*先将p的右孩子赋值给temp的右孩子*/
        temp.setrChild(p.getrChild());
        /*再将temp赋值给p的右孩子*/
        p.setrChild(temp);
    }

    @Override
    public TreeNode<E> deleteL(TreeNode<E> p) {
        /*如果节点p本身为空或者p的左子树为空，则删除null*/
        if (p == null || p.getlChild() == null){
            return null;
        }
        //先得到p的左子树，再将p的左孩子设置为空
        TreeNode<E> temp = p.getlChild();  //temp是用来返回的节点
        p.setlChild(null);
        return temp; //返回删除的节点
    }

    @Override
    public TreeNode<E> deleteR(TreeNode<E> p) {
        return null;
    }

    @Override
    public TreeNode<E> search(TreeNode<E> root, E val) {
        TreeNode<E> p = root;
        //1. 先判断root是否为空，如果为null，则返回null
        if (p == null){
            return null;
        }
        //2.如果根结点的值为val，直接返回val
        if (p.getData().equals(val)){
            return p;
        }
        //3.如果2不成功，找根结点的左孩子
        TreeNode<E> temp = null;
        if (p.getlChild()!= null){
            temp = search(p.getlChild(),val);
        }
        //如果左子树找到val的结点，则直接返回该结点
        if (temp != null){
            return temp;
        }
        //4. 找root根结点的右孩子
        if (p.getrChild() != null){
            temp = search(p.getrChild(),val);
        }
        return temp;
    }

    //遍历
    @Override
    public void traverse(TreeNode<E> root, int i) {
      if (i == 1){
          preorder(root);
      }
    }


    //获得根结点的方法

    public TreeNode<E> getHead() {
        return head;
    }

    public void setHead(TreeNode<E> head) {
        this.head = head;
    }

    //先序
    public void preorder(TreeNode<E> p){
        //先判断是否为空
        if (isEmpty()){
            System.out.println("二叉树为空");
            return;
        }
        //遍历
        if (p != null){
            //先根
            System.out.println(p.getData());
            //左
            preorder(p.getlChild());
            //右
            preorder(p.getrChild());
        }
    }
    public boolean isEmpty(){
        return head == null;
    }

    public void minorder(TreeNode<String> p){
        //先判断是否为空
        if (isEmpty()){
            System.out.println("二叉树为空");
            return;
        }
        //遍历
        if (p != null){

            //左
            minorder(p.getlChild());
            //先根
            System.out.println(p.getData());
            //右
            minorder(p.getrChild());
        }
    }
}
